package pro.softzhang.algo.lc400;

import java.util.Arrays;

/**
 * 435. 无重叠区间
 * https://leetcode.cn/problems/non-overlapping-intervals
 */
public class LC435_NonOverlappingIntervals {
    public static void main(String[] args) {
        int[][]intervals = {{1,2}, {2,3}, {3,4}, {1,3}};
        System.out.println(new Solution().eraseOverlapIntervals(intervals));
    }

    /**
     * https://leetcode.cn/problems/non-overlapping-intervals/solutions/2564483/da-bai-hua-jiang-tan-xin-si-lu-tong-su-y-sjnb/
     */
    static
    class Solution {
        public int eraseOverlapIntervals(int[][] intervals) {
            Arrays.sort(intervals, (a, b) -> {
                if (a[1] == b[1]) {
                    return a[0] - b[0];
                }
                return a[1] - b[1];
            });
            int n = intervals.length, ret = 0;
            int[] prev = intervals[0];
            for (int i = 1; i < n; i++) {
                int r = prev[1], l = intervals[i][0];
                if (l < r) {
                    ret++;
                } else {
                    prev = intervals[i];
                }
            }
            return ret;
        }
    }
}
